package 数据结构.树;


import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-25
 */
public class JZ55二叉树的深度 {
    //递归
    /*
    *   终止条件： 当进入叶子节点后，再进入子节点，即为空，没有深度可言，返回0.
        返回值： 每一级按照上述公式，返回两边子树深度的最大值加上本级的深度，即加1.  max(depthL,depthR)+1
        本级任务： 每一级的任务就是进入左右子树，求左右子树的深度。
        *
        * step 1：对于每个节点，若是不为空才能累计一次深度，若是为空，返回深度为0.
        step 2：递归分别计算左子树与右子树的深度。
        step 3：当前深度为两个子树深度较大值再加1。
    * */
    public int TreeDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        return  Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
    }


    //层次遍历  队列

    /**
     * step 1：既然是层次遍历，我们遍历完一层要怎么进入下一层，可以用队列记录这一层中节点的子节点。
     * step 2：在刚刚进入某一层的时候，队列中的元素个数就是当前层的节点数。
     *          比如第一层，根节点先入队，队列中只有一个节点，对应第一层只有一个节点，
     *          第一层访问结束后，它的子节点刚好都加入了队列，此时队列中的元素个数就是下一层的节点数。
     *          因此遍历的时候，每层开始统计该层个数，然后遍历相应节点数，精准进入下一层。
     * step 3：遍历完一层就可以节点深度就可以加1，直到遍历结束，即可得到最大深度。
     */
    public int TreeDepth2(TreeNode root) {
        if(root == null)
            return 0;
        Queue<TreeNode> q = new LinkedList<>();
        //根入队
        q.offer(root);
        int depth = 0;
        while(!q.isEmpty()){
            //记录当前层有多少节点
            int n = q.size();
            for(int i =0; i<n;i++){
                TreeNode node = q.poll();
                if(node.left!=null)
                    q.offer(node.left);
                if(node.right!=null)
                    q.offer(node.right);
            }
            depth++;
        }

        return depth;
    }
}
